package com.itheima.leetcode.od.b.dynamicprogramming;

import java.util.*;
import java.util.stream.Collectors;

/**
 * <h3>Leetcode139-单词拆分（有点类似Leetcode300-最长递增子序列）</h3>
 */
public class WordBreakLeetcode139 {

    public static void main(String[] args) {
        String leetcode = "leetcode";
        ArrayList<String> wordDict = Arrays.stream("[\"leet\", \"code\"]"
                .replace("[", "")
                .replace("]", "")
                .replace("\"", "")
                .split(", "))
                .collect(Collectors.toCollection(ArrayList::new));

        System.out.println(wordBreak(leetcode, wordDict));
    }

    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1]; // 坐标 i 代表的是长度（而非传统的坐标），所以 dp 长度是 s.length() + 1
        dp[0] = true; // 0长度匹配 肯定为 true 啊
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
